
//旋转链表
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(!head || !(head->next) || 0 == k)
        return head;
        int length = 0;
        ListNode* back = head;//记录链表的最后一个节点
        //先算出链表的长度
        while(back->next)
        {
            back = back->next;
            ++length;
        }
        //链表的长度等于length+1
        length += 1;
        int pos = k % length;
        if(0 == pos) //如果模运算的结果为0那么就说明无需对链表进行旋转
        return head;
        ListNode* prev = nullptr;//必须将链表处的节点
        ListNode* insert_node = head;
        for(int i = 1; i <= length-pos ; ++i)
        {
            prev = insert_node;
            insert_node = insert_node->next;
        }
        prev->next = nullptr;
        back->next = head;
        return insert_node;

        //不断的头插就可以了
        //第一次旋转链表
        // ListNode* re_head = nullptr;
        // ListNode* cur = head;
        // while(cur)
        // {
        //     ListNode* tmp = cur->next;
        //     cur->next = re_head;
        //     re_head = cur;
        //     cur = tmp;
        // }
        // ListNode* re_prev = re_head;
        // ListNode* re_back = head;
        // while(k--)
        // {
        //     ListNode* insert_node = re_prev;
        //     re_prev = re_prev->next;
        //     insert_node->next = nullptr;//注意要将待插入节点的next置空(否则会呈环形)
        //     re_back->next = insert_node;
        //     re_back = re_back->next;
        // }
        // //再将链表反转
        // re_head = nullptr;
        // cur = re_prev;
        // while(cur)
        // {
        //     ListNode* tmp = cur->next;
        //     cur->next = re_head;
        //     re_head = cur;
        //     cur = tmp;
        // }
        // return re_head;
    }
};